Where managed pointers live?

Synopsis

Garabage collector have to resolve managed pointers to their objects when a specified managed pointer refers to the heap. In rotor's implementation this is expensive task. I shell try to investigate whether it's possible in some (many) cases to resolve managed pointer in a way faster then scanning heap.

Rationale

I believe in many cases source object of managed pointer are refered in the same or some ancestor's stack frame as managed pointer.

...

Implementation

I've modified JIT "promotion" callback in garbage collector in order it would try to resolve managed pointers using objects that occur in the stack frame and only if this algorithm would fail, would resolve managed pointers with "find in the heap" algorithm.

The goal of this implementation is:

• to be as light as possible (at least in case of objects).
• to resolve most of managed pointers that appear.

In short algorithm works as following:

• Callback that routes all stack items (more precisely stack items of JITed code) now contains a filter that collects managed pointers and objects.
• Objects are promoted immediately, managed pointers however are either promoted after all objects in the stack frame or their promotion is delayed until next stack frame.
• The decision of whether to promote managed pointers depends on whether an object which contains refered area occurs in the stack frame. If such object appears, the managed pointer is promoted, otherwise if managed pointer is a method's argument then its promotion is delayed.
• All adjacent and contained managed pointers are grouped in order to be resolved as whole unit. (In order to implement this rule, filter have to know sizes of values to which managed pointers refer. This information is now provided by JIT as part of JitInfo along with bit runs that describe state of stack.)
• If it's not possible to resolve group of managed pointers using above rules then "find in the heap" algorithm is used.

The algorithm has really short path for object, just a several simple conditions (in average is only couple) and a bit more complicated logic for managed pointer, but it inteded to resolve it!

Tests and results

There were several aspects in testing:

• create working sample that shows advantage of the algorithm;
• find sample that works more slowly then original algorithm (this was expected);
• find examples in bcl that would benefit (lose) from this algorithm.

It was pretty easy to create more fast sample: if we have object that contains field of structure type and call any method on this field value we get "this" as managed pointer; or even more simple example when we pass field address as ref argument to the function.

The advantage in such examples varies from -0 to 10% this mainly depends on how fast original "find in the heap" algorithm finds the object. -0 hear means that in extremely successful case "find in the heap" algorithm finds the result just from the first try.

On the other hand when stack does not contains managed pointer (to heap) at all results are just equal.

And finally there is a class of cases when the resolving algorithm fails and "find in the heap" algorithm is invoked. In this case result could be about 2% - 3% slower. I believe however that patterns that lead to such a slow program are quite unnatural.

And finnaly I was trying to find samples in bcl that prove my hypothesis. To my disappointment I've found that bcl carefully avoids using managed pointers (directly and inderectly) at all! This is probably why there is conception in bcl that value types are init only. As result accounting probability of appearing of managed pointer in code the final result is very very similar to original implementation. It's looks like I've made code bigger without anysignificant result!

Conclusion

I admit that the problem I've discussed(?) here probably is not so sharp as I allowed in the first place. All related code I've separated in branch "Resolving-interiors" in vm and fjit subprojects. I still belive that this realy was beautiful algorithm.

Share your thoughts with as about this article.